// 动态规划算法集合
class DynamicProgramming {
  // 斐波那契数列 - 递归 + 记忆化
  fibonacci(n) {
    // TODO: 实现斐波那契数列
    // 返回第 n 个斐波那契数
  }

  // 斐波那契数列 - 迭代版本
  fibonacciIterative(n) {
    // TODO: 实现斐波那契数列的迭代版本
    // 返回第 n 个斐波那契数
  }

  // 爬楼梯问题
  climbStairs(n) {
    // TODO: 实现爬楼梯问题
    // 每次可以爬 1 或 2 个台阶，返回爬到第 n 阶的方法数
  }

  // 最长公共子序列 (LCS)
  longestCommonSubsequence(text1, text2) {
    // TODO: 实现最长公共子序列
    // 返回两个字符串的最长公共子序列的长度
  }

  // 最长递增子序列 (LIS)
  longestIncreasingSubsequence(nums) {
    // TODO: 实现最长递增子序列
    // 返回数组中最长递增子序列的长度
  }

  // 编辑距离 (Levenshtein Distance)
  editDistance(word1, word2) {
    // TODO: 实现编辑距离
    // 返回将 word1 转换为 word2 所需的最少操作数
  }

  // 0-1 背包问题
  knapsack(weights, values, capacity) {
    // TODO: 实现 0-1 背包问题
    // 返回在给定容量下能获得的最大价值
  }

  // 硬币找零问题
  coinChange(coins, amount) {
    // TODO: 实现硬币找零问题
    // 返回组成给定金额所需的最少硬币数，如果无法组成返回 -1
  }

  // 最大子数组和 (Kadane's Algorithm)
  maxSubArray(nums) {
    // TODO: 实现最大子数组和
    // 返回数组中连续子数组的最大和
  }

  // 最长回文子序列
  longestPalindromeSubseq(s) {
    // TODO: 实现最长回文子序列
    // 返回字符串中最长回文子序列的长度
  }

  // 矩阵路径问题
  uniquePaths(m, n) {
    // TODO: 实现矩阵路径问题
    // 返回从左上角到右下角的唯一路径数
  }

  // 最小路径和
  minPathSum(grid) {
    // TODO: 实现最小路径和
    // 返回从左上角到右下角的最小路径和
  }
}

module.exports = DynamicProgramming
